<!DOCTYPE html>  
<html>
    <meta charset="utf-8" />  
    <title>树</title>  
<body>
    <h2>树</h2>
    <p>
        树是一种非顺序数据结构，一种分层数据的抽象模型，
        它对于存储需要快速查找的数据非常有用。
    </p>
</body>
<script>  
    // 二叉搜索树（BST）是二叉树的一种，但是它只允许你在左侧节点存储（比父节点）小的值， 
    // 在右侧节点存储（比父节点）大（或者等于）的值。上图中就展现了一棵二叉搜索树。
    class Node{
        constructor(key){
            this.key = key;
            this.left = null;
            this.right = null;
        }
    }
    class BinarySearchTree {
        constructor(){
            this.root = null;
        }
        insert(key){
            const newNode = new Node(key);
            const insertNode = (node,newNode)=>{
                if(newNode.key<node.key){
                    if(node.left === null){
                        node.left = newNode
                    }else{
                        insertNode(node.left,newNode)
                    }
                }else{
                    if(node.right === null){
                        node.right = newNode
                    }else{
                        insertNode(node.right,newNode)
                    }
                }
            }
            if(!this.root){
                this.root = newNode;
            }else{
                insertNode(this.root,newNode)
            }
        }
        // 访问树的所有节点有三种方式：中序、先序、后序。
        // 中序遍历  中序遍历是一种以上行顺序访问 BST 所有节点的遍历方式，也就是以从最小到最大的顺序访 问所有节点
        inOrderTraverse(callback) {
            const inOrderTraverseNode = (node, callback) => {
                if (node !== null) {
                    inOrderTraverseNode(node.left, callback)
                    callback(node.key)
                    inOrderTraverseNode(node.right, callback)
                }
            }
            inOrderTraverseNode(this.root, callback)
        }
        //先序遍历  先序遍历是以优先于后代节点的顺序访问每个节点的。先序遍历的一种应用是打印一个结构化的文档。
        preOrderTraverse(callback) {
            const preOrderTraverseNode = (node, callback) => {
                if (node !== null) {
                    callback(node.key)
                    preOrderTraverseNode(node.left, callback)
                    preOrderTraverseNode(node.right, callback)
                }
            }
            preOrderTraverseNode(this.root, callback)
        }
        // 后序遍历  后序遍历则是先访问节点的后代节点，再访问节点本身。后序遍历的一种应用是计算一个目录和它的子目录中所有文件所占空间的大小。
        postOrderTraverse(callback) {
            const postOrderTraverseNode = (node, callback) => {
                if (node !== null) {
                    postOrderTraverseNode(node.left, callback)
                    postOrderTraverseNode(node.right, callback)
                    callback(node.key)
                }
            }
            postOrderTraverseNode(this.root, callback)
        }
        // 查询最小值
        min(node){
            const minNode =node=>node?(node.left?minNode(node.left):node):null;
            return minNode(node||this.root)
        }
        // 查询最大值
        max(node){
            const maxNode =node=>node?(node.right?maxNode(node.right):node):null;
            return maxNode(node||this.root)
        }
        // 搜索一个特定的值
        search(key) {
            const searchNode = (node, key) => {
                if (node === null) return false
                if (node.key === key) return node
                return searchNode((key < node.key) ? node.left : node.right, key)
            }
            return searchNode(this.root, key)
        }
        // 移除一个节点
        remove(key){
            const removeNode=(node,key)=>{
                if(node===null){return null}
                if(key<node.key){
                    node.left = removeNode(node.left,key);
                    console.log('nnnnnnnnnnnnnnnnnnn',node)
                    return node;
                }else if(key>node.key){
                    node.right = removeNode(node.right,key);
                    return node;
                }else{
                    if(node.left==null&&node.right==null){
                        node = null;
                        return node;
                    } 
                    if(node.left==null){
                        node = node.right;
                        return node;
                    }else if(node.right == null){
                        node = node.left;
                        return node;
                    }

                    var aux = this.findMinNode(node.right); 
                    node.key = aux.key;
                    node.right = removeNode(node.right, aux.key);
                    return node;
                }
            }
            return removeNode(this.root,key)
        }
        // 找到右侧最小的节点
        findMinNode(node){
            while (node && node.left !== null) {
                node = node.left;
            }
            return node;
        }
    }
    const tree = new BinarySearchTree();
    tree.insert(11)
    tree.insert(7)
    tree.insert(5)
    tree.insert(6)
    tree.insert(9)
    tree.insert(8)
    tree.insert(1)
    tree.insert(2)
    tree.insert(14)
    tree.insert(12)
    tree.insert(16)

    console.log('root',tree.root)

    tree.inOrderTraverse((value)=>console.log('中序遍历',value))
    tree.preOrderTraverse((value)=>console.log('先序遍历',value))
    tree.postOrderTraverse((value)=>console.log('后序遍历',value))

    console.log('min',tree.min())
    console.log('max',tree.max())
    console.log('search',tree.search(2))
    console.log('remove',tree.remove(1))

</script>  
</html>